package com.leetcode.partition1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/8/13 21:44
 */
public class LC40组合总和2 {

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        //相比leetcode39题，每个元素只能选一次且要考虑去重，如果在最后结果时进行判断去重，代码提交会超时，因此需要使用used数组来记录已经使用的元素
        //同一树层上相同的两个重复元素不可以重复选取
        boolean[] used = new boolean[candidates.length];
        backtracking(result, new ArrayList<>(), 0, candidates, target, 0, used);
        return result;
    }

    public static void main(String[] args) {
        int[] candidates = { 2, 5, 2, 1, 2 };
        int target = 5;
        System.out.println(combinationSum2(candidates, target));
    }

    private static void backtracking(List<List<Integer>> result, List<Integer> path, int startIndex, int[] candidates, int target, int sum, boolean[] used) {
        if (sum == target) {
            if (!result.contains(path)) result.add(new ArrayList<>(path));
            return;
        }
        //同层遍历
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            //used[i - 1] == true，说明同一树枝candidates[i - 1]使用过；used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
            path.add(candidates[i]);
            used[i] = true;
            backtracking(result, path, i + 1, candidates, target, sum + candidates[i], used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}
